package 剑指offer突击版;

/**
 * 整数除法
 *
 * 给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%' 。
 *
 * 思路：那就得使用位运算符了， 但是也可以这样想，可以使用二分法，接近查找，也是能解决的，但是二分的时候也是需要使用位运算符号的。
 *  快速相减法
 */
public class SII001 {
    public int divide(int a, int b) {
        // 特殊情况1,b=1
        if (b == 1) {
            return a;
        }
        // 特殊情况2，b=-1
        if (b == -1) {
            return a == Integer.MIN_VALUE ? Integer.MAX_VALUE : -a;
        }
        // 特殊情况3，a=0
        if (a == 0) {
            return 0;
        }
        //确定符号
        boolean positive = (a ^ b) >= 0;
        // 为了避免溢出，转为负数进行计算
        a = a < 0 ? a : -a;
        b = b < 0 ? b : -b;
        // 快速相减
        int quotitent = 0;
        while (a <= b) {
            int base = 1;
            int divisor = b;
            // 使用减法，避免溢出
            while (a - divisor <= divisor) {
                divisor <<= 1;
                base <<= 1;
            }
            quotitent += base;
            a -= divisor;
        }
        return positive ? quotitent : -quotitent;
    }
}
